First missing positive [Tricky]

Time: O(N); Space: O(1); hard

Given an unsorted integer array, find the first missing positive integer.

Example 1:

Input: nums = [1,2,0]

Output: 3

Example 2:

Input: nums = [3,4,-1,1]

Output: 2

Example 3:

Input: nums = [7,8,9,11,12]

Output: 1

Your algorithm should run in O(n) time and uses constant space.

Hints:

  1. Think about how you would solve the problem in non-constant space. Can you apply that logic to the existing space?

  2. We don’t care about duplicates or non-positive integers

  3. Remember that O(2N) = O(N)

[1]:

class Solution1(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = 0
        while i < len(nums):
            if nums[i] > 0 and nums[i] - 1 < len(nums) and nums[i] != nums[nums[i]-1]:
                nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
            else:
                i += 1

        for i, integer in enumerate(nums):
            if integer != i + 1:
                return i + 1

        return len(nums) + 1

[2]:

s = Solution1()
nums = [1, 2, 0]
assert s.firstMissingPositive(nums) == 3
nums = [3, 4, -1, 1]
assert s.firstMissingPositive(nums) == 2
nums = [7, 8, 9, 11, 12]
assert s.firstMissingPositive(nums) == 1